class Solution:
    def merge(self,list1,list2):#合并两个有序数组，使用额外空间
        result=[]
        i,j=0,0
        while(i<len(list1) and j<len(list2)):
            if(list1[i]<list2[j]):
                result.append(list1[i])
                i+=1
            else:
                result.append(list2[j])
                j+=1
        result+=list1[i:]#避免丢失list1中的元素
        result+=list2[j:]
        return result
    def sortArray(self, nums):
        #递归终止条件
        if(len(nums)<=1):
            return nums
        left=0
        right=len(nums)
        mid=(left+right)//2
        #递归，分治
        x1=self.sortArray(nums[0:mid])
        x2=self.sortArray(nums[mid:])
        print(x1,x2)
        return self.merge(nums[0:mid],nums[mid:])
if __name__ == '__main__':
    s=Solution()
    print(s.sortArray([5,2,3,1]))
    l=[1,2,3,4]
    print(l[::-1])